package ex.algorithms.sorting;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class BucketSort {
	public static double[] sortIncreasing(double[] input) {
		if(input == null || input.length < 2)
			return input;
		
		ArrayList[] buckets = new ArrayList[input.length];
		for(int i=0; i<input.length; i++) {
			int index = (int) (input.length * input[i]);
			ArrayList list = buckets[index]; 
			if(list == null)
				list = new ArrayList();
			list.add(input[i]);
			buckets[index] = list;
		}
		
		double[] output = new double[input.length];
		int counter = 0;
		for(int i=0; i<buckets.length; i++) {
			if(buckets[i] == null)
				continue;
			
			Collections.sort(buckets[i]);
			for(Object element: buckets[i]) {
				output[counter] = (Double) element;
				counter ++;
			}
		}
		
		return output;
	}
}
